package 链表;

import com.sun.org.apache.bcel.internal.generic.NEW;

/**
 * https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
 */
public class _25_K个一组翻转链表 {
    public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }


    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        //区间[a,b)包含k个待反转的元素
        ListNode a,b;
        a = b = head;
        for(int i=0;i<k;++i){
            //该区间不足k个，不需要反转,base case，直接返回即可
            if(b == null) return head;
            b = b.next;
        }
        //先反转前两个,拿到反转后的头节点
        ListNode newHead = reverse(a,b);
        //更小的子问题,从b开始，在此反转k个节点
        a.next = reverseKGroup(b,k);

        return newHead;
    }

    //函数定义:反转[a,b)之间的链表
    private ListNode reverse(ListNode a,ListNode b){
        ListNode newHead,cur,next;
        newHead = null;
        cur = a;
        next = a;
        while(cur!=b){
            next = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = next;
        }
        return newHead;
    }
}
